package epam.com.rd.MyCollections;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.RandomAccess;

public class MyCollections {

	public static void sort(MyList list) {
		Object[] arr = list.toArray();
		if (list instanceof RandomAccess) {
			quickSort(arr, 0, arr.length - 1);
			list.clear();
			list.addAll(arr);
		} else
			insertionSort(arr);
		list.clear();
		list.addAll(arr);

	}

	private static void insertionSort(Object[] list) {
		for (int index = 1; index < list.length; index++) {
			Object key = list[index];
			int position = index;
			while (position > 0
					&& ((Comparable) key).compareTo(list[position - 1]) < 0) {
				list[position] = list[position - 1];
				position--;
			}

			list[position] = key;
		}
	}

	private static void quickSort(Object[] array, int lowIndex, int highIndex) {

		if (lowIndex >= highIndex) {
			return;
		}

		int pivotIndex = getPivot(lowIndex, highIndex);
		Object pivot = array[pivotIndex];
		swapItemsWithIndices(array, pivotIndex, highIndex);

		int i = lowIndex - 1;
		int j = highIndex;
		do {
			do {
				i++;
			} while (((Comparable) array[i]).compareTo(pivot) < 0);
			do {
				j--;
			} while (((Comparable) array[j]).compareTo(pivot) > 0
					&& (j > lowIndex));
			if (i < j) {
				swapItemsWithIndices(array, i, j);
			}
		} while (i < j);

		swapItemsWithIndices(array, highIndex, i);
		quickSort(array, lowIndex, i - 1);
		quickSort(array, i + 1, highIndex);
	}

	private static void swapItemsWithIndices(Object[] arr, int firstItem,
			int secondItem) {
		final Object tempItem = arr[firstItem];
		arr[firstItem] = arr[secondItem];
		arr[secondItem] = tempItem;
	}

	private static int getPivot(int lowIndex, int highIndex) {
		return lowIndex + ((highIndex - lowIndex) / 2);
	}

	public static void sort(MyList list, Comparator c) {
		Object[] arr = list.toArray();
		Arrays.sort(arr, (Comparator) c);
		list.clear();
		list.addAll(arr);
	}

	public static void swap(MyList list, int i, int j) {
		if (!(i >= 0 && i < list.size()) || !(j >= 0 && j < list.size()))
			throw new MyIndexOutOfBoundsException("Index out of bounds");

		if (i == j)
			return;

		Object[] arr = list.toArray();
		Object tmpObject = arr[i];
		arr[i] = arr[j];
		arr[j] = tmpObject;
		list.clear();
		list.addAll(arr);

	}

	public static void copy(MyList dest, MyList src) {
		if (src.isEmpty())
			return;
		Object[] arrSrc = src.toArray();
		dest.addAll(arrSrc);
	}

	public static void reverse(MyList list) {
		if (list.isEmpty()) {
			return;
		}
		Object[] arrObjects = list.toArray();
		int i = 0;
		int j = arrObjects.length - 1;
		Object tmpObject;
		while (j > i) {
			tmpObject = arrObjects[j];
			arrObjects[j] = arrObjects[i];
			arrObjects[i] = tmpObject;
			j--;
			i++;
		}
		list.clear();
		list.addAll(arrObjects);

	}

	public static int binarySearch(MyList list, Object key) {
		int low = 0;
		int high = list.size() - 1;
		while (low <= high) {
			int mid = (low + high) >>> 1;
			Comparable midVal = (Comparable) list.get(mid);
			int cmp = midVal.compareTo(key);

			if (cmp < 0)
				low = mid + 1;
			else if (cmp > 0)
				high = mid - 1;
			else
				return mid;
		}
		return -(low);
	}

}
